package com.lw.leetcode.tree.c;

import com.lw.leetcode.tree.TreeNode;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 2458. 移除子树后的二叉树高度
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/31 15:22
 */
public class TreeQueries {

    public static void main(String[] args) {
        TreeQueries test = new TreeQueries();
        // {0=[12884901889], 1=[12884901893], 2=[12884901891], 3=[12884901890, 12884901892]}
        //
        //{1=0, 2=3, 3=2, 4=3, 5=1}
        Long v = 12884901893L;
        int h = (int) (v >> 32);
        int t = v.intValue();
        System.out.println(h);

        System.out.println(t);
    }

    private Map<Integer, List<Long>> as = new HashMap<>();
    private Map<Integer, Integer> hs = new HashMap<>();

    public int[] treeQueries(TreeNode root, int[] queries) {
        find(root, 0);
        for (Map.Entry<Integer, List<Long>> entry : as.entrySet()) {
            Collections.sort(entry.getValue());
        }
        int length = queries.length;
        int[] values = new int[length];
        for (int i = 0; i < length; i++) {
            int query = queries[i];
            Integer c = hs.get(query);
            List<Long> list = as.get(c);
            int size = list.size();
            Long v = list.get(size - 1);
            int h = (int) (v >> 32);
            int t = v.intValue();

            if (size == 1) {
                values[i] = c - 1;
                continue;
            }
            if (t != query) {
                values[i] = h;
                continue;
            }
            values[i] = (int) Math.max(c - 1, list.get(size - 2) >> 32);
        }
        return values;
    }

    private int find(TreeNode node, int s) {
        if (node == null) {
            return 0;
        }
        int a = find(node.left, s + 1);
        int b = find(node.right, s + 1);
        a = Math.max(a, b);
        long l = ((long) (a + s) << 32) + node.val;
        as.computeIfAbsent(s, v -> new ArrayList<>()).add(l);
        hs.put(node.val, s);
        return a + 1;
    }

}
